<!-- The documentation for converting a grammar to CNF form. -->

<HTML><HEAD>
<TITLE>Chomsky Converter</TITLE>
</HEAD><BODY>

<H1>Chomsky Converter</H1>

<P ALIGN="center"><IMG SRC="images/transform/chomsky.png" ALT="Unit production remover" WIDTH="386" HEIGHT="357" BORDER="1"></P>

<P>This action is the final of four steps in transforming a grammar to Chomsky normal form (CNF).  The goal is to reform the grammar so that it generates the same language as the original, but is in Chomsky normal form.  A grammar in Chomsky normal form (CNF) has all productions be either to two variables, or a single terminal.</P>

<P>The converter works as follows: the user starts with the original grammar, and repeatedly converts productions that are not CNF already.  It works rather simply on two cases.</P>

<P>The first case is if a production has multiple symbols in its right hand side with at least one of those symbols as a terminal.  In this case, any terminal symbols are converted to variables like so: for any terminal <VAR><IMG SRC="entities/alpha.png" WIDTH="9" HEIGHT="9" ALIGN="middle"></VAR>, a production <VAR>B(<IMG SRC="entities/alpha.png" WIDTH="9" HEIGHT="9" ALIGN="middle">)<IMG SRC="entities/rarr.png" WIDTH="16" HEIGHT="7" ALIGN="middle"><IMG SRC="entities/alpha.png" WIDTH="9" HEIGHT="9" ALIGN="middle"></VAR> will be introduced, and the variable <VAR>B(<IMG SRC="entities/alpha.png" WIDTH="9" HEIGHT="9" ALIGN="middle">)</VAR> will replace <VAR><IMG SRC="entities/alpha.png" WIDTH="9" HEIGHT="9" ALIGN="middle"></VAR> in the original production.</P>

<P>The second case is if a production has more than two variables in its right hand side, but no terminals.  For example, take <VAR>A<IMG SRC="entities/rarr.png" WIDTH="16" HEIGHT="7" ALIGN="middle">BCDE</VAR>.  In this case, that production is replaced with the two productions <VAR>A<IMG SRC="entities/rarr.png" WIDTH="16" HEIGHT="7" ALIGN="middle">BD(n)</VAR> and <VAR>D(n)<IMG SRC="entities/rarr.png" WIDTH="16" HEIGHT="7" ALIGN="middle">CDE</VAR>, where <VAR>n</VAR> is some positive integer.  One would then have to convert the <VAR>D(n)<IMG SRC="entities/rarr.png" WIDTH="16" HEIGHT="7" ALIGN="middle">CDE</VAR> production.</P>

<P>This process is repeated until there are no productions that are not in CNF form.</P>

<P>As a note, the CNF converter will attempt to introduce as few new productions as it can, and will attempt to reuse existing variables and productions wherever possible.</P>

<H2>Help & Controls</H2>

<P>"Convert Selected" will take any production currently selected in the grammar editing view, and break it down via the method listed above; double clicking on a production accomplishes the same effect.  "Do All" will make the grammar CNF in one fell swoop.  "What's Left?" will highlight those productions that remain to be converted.  "Export" is available only when the grammar is CNF, and will take this reformed grammar and put it in its own window.</P>

</BODY></HTML>
